/LMAR=0/XLINE=3/FONT#0=BAXL30/FONT#1=BAXM30/FONT#2=BAXB30/FONT#3=SUB/FONT#4=SUP/FONT#5=BASL35/FONT#6=NGR25/FONT#7=MATH30/FONT#8=FIX25/FONT#9=GRK30



␈↓ ↓H␈↓CS206␈↓ ¬_MIDTERM EXAMINATION␈↓ 
0FALL 1977 

␈↓ ↓H␈↓␈↓ α_This␈α
examination␈α
is␈α
open␈α
book␈α
and␈α∞notes.␈α
 Write␈α
LISP␈α
functions␈α
as␈α
follows␈α∞except␈α
where
␈↓ ↓H␈↓something else is requested.  Either notation may be used.

␈↓ ↓H␈↓1. ␈↓↓depth x␈↓ is the length of the longest ␈↓↓car-cdr␈↓ chain reaching an atom in the S-expression ␈↓↓x.␈↓

␈↓ ↓H␈↓2.␈αLet␈α␈↓↓u␈↓␈αbe␈αa␈αlist,␈α␈↓↓f␈↓␈αa␈αfunction␈αon␈αlist␈αelements␈αand␈α␈↓↓p␈↓␈αa␈αpredicate␈αon␈αlist␈αelements.␈α ␈↓↓mapcat[u,f,p]␈↓
␈↓ ↓H␈↓is the obtained by appending elements ␈↓↓f[x]␈↓ of ␈↓↓u␈↓ such that ␈↓↓p[x]␈↓ is satisfied.

␈↓ ↓H␈↓3.␈αLet␈α
␈↓↓g␈↓␈αbe␈α
a␈αdirected␈α
graph␈αin␈α
notation␈αdescribed␈αin␈α
the␈αnotes.␈α
 (It␈αis␈α
a␈αlist␈α
of␈αsublists,␈αeach␈α
sublist
␈↓ ↓H␈↓consisting␈αof␈α
a␈αvertex␈α
followed␈αby␈αthe␈α
vertices␈αto␈α
which␈αit␈αis␈α
connected.␈α ␈↓↓component[x,g]␈↓␈α
is␈αa␈αlist␈α
of
␈↓ ↓H␈↓the␈αvertices␈αwhich␈αmay␈αbe␈αreached␈αfrom␈αthe␈αvertex␈α␈↓↓x␈↓␈αby␈αa␈αpath␈αin␈αthe␈αgraph.␈α ␈↓↓bigcomponent[x,g]␈↓
␈↓ ↓H␈↓is a list of all the vertices to which ␈↓↓x␈↓ is connected by any combination of paths.

␈↓ ↓H␈↓4.␈αLet␈α␈↓↓successors␈αx␈↓␈αbe␈αthe␈αlist␈αof␈αsuccessors␈αof␈αan␈αelement␈α␈↓↓x␈↓␈αin␈αsome␈αsearch␈αspace,␈αi.e.␈αthey␈αare␈αthe
␈↓ ↓H␈↓elements␈αof␈αthe␈αspace␈αthat␈αcan␈αbe␈αreached␈αfrom␈α␈↓↓x␈↓␈αin␈αone␈αmove.␈α ␈↓↓bsearch[x,p]␈↓␈αis␈αan␈αelement␈αof␈αthe
␈↓ ↓H␈↓space satisfying the predicate ␈↓↓p␈↓ and at the lowest depth in the tree.